package library;
import java.util.Arrays;

public class GrahamScan {
	
	Point minPoint, stopPoint;

	//Find the bottom left point and run grahamScan
	void grahamScan(Point[] points){
		minPoint = null;
		for(Point p : points)
			if(minPoint==null || p.y<minPoint.y || (p.y==minPoint.y && p.x <minPoint.x))
				minPoint = p;		
		grahamScan(points,minPoint);
	}

	//minPoint = bottom, left point
	void grahamScan(Point[] points, Point minPoint) {
		Arrays.sort(points);
		stopPoint = points[points.length-1];

		int m = 1;
		for(int i = 2; i <points.length; i++){
			while(crossProduct(points[m-1],points[m-1],points[m],points[i])<=0)
				if(m==1)	//Check if first points are collinear, if so ignore unnecessary points.
					points[m]=points[i++];
				else
					m--;
			points[++m]=points[i];
		}
	}

	public int crossProduct(Point start1, Point start2, Point end1, Point end2){
		double crossProduct = (end1.x-start1.x)*(end2.y-start2.y)-(end1.y-start1.y)*(end2.x-start2.x);
		return crossProduct < -1E-6 ? -1 : (crossProduct > 1E-6 ? 1 : 0);
	}

	class Point implements Comparable<Point>{
		double x,y, dist, cos;
		boolean vals = false;

		public Point(double x, double y){
			this.x = x; this.y = y;
		}

		public void setVals(){
			vals = true;
			this.dist =  (x-minPoint.x)*(x-minPoint.x)+(y-minPoint.y)*(y-minPoint.y);
			this.cos = (x-minPoint.x)/Math.sqrt(dist);
		}
		@Override
		public int compareTo(Point arg0) {
			if(!vals)
				this.setVals();
			if(!arg0.vals)
				arg0.setVals();

			if(Math.abs(cos - arg0.cos) > 1e-6)
				return (int)((arg0.cos-cos)*1000000);
			else
				return (int)((dist-arg0.dist)*1000000);
		}
	}
}
